package test;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @title: test404
 * @Author: wangzijun
 * @description:
 * @version: 1.0.0
 * @CreateTime: 2022-09-12  11:04
 */


public class test404 {
   public static int[] arr={3,9,0,0,20,15,0,0,7,0,0};
   public static int index=0;
   public static void main(String[] args) {
       TreeNode T=new TreeNode();

       T=createTree();
       preTravel(T);
       System.out.println();
       System.out.println(sumOfLeftLeaves(T));

       System.out.println(dfs(T));
       System.out.println(bfs(T));
   }
   public static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
   }

   public static TreeNode createTree(){
      if(arr[index]==0){
       index++;
        return null;
    }else{
        TreeNode T1=new TreeNode();
        T1.val=arr[index];
        index++;
        T1.left=createTree();
        T1.right=createTree();
        return T1;
      }
   }

   public static void preTravel(TreeNode T){
      if(T==null) return;
      preTravel(T.left);
      System.out.print(T.val+" ");
      preTravel(T.right);
   }
   public static int sumOfLeftLeaves(TreeNode T){
      int ans=0;
      if(T==null) return 0;
      if(T.left!=null&&T.left.left==null&&T.left.right==null){
          ans+=T.left.val;
      }
      return ans+sumOfLeftLeaves(T.left)+sumOfLeftLeaves(T.right);
   }


   public static int dfs(TreeNode T){
       int sum=0;
       if(T.left!=null){
           if(T.left.left==null&&T.left.right==null){
               sum+=T.left.val;
           }else{
               sum+=dfs(T.left);
           }
       }
       if(T.right!=null){
           sum+=dfs(T.right);
       }
       return sum;
   }

   public static int bfs(TreeNode T){
       int count=0;
       if(T==null) return 0;
       Deque<TreeNode> q=new ArrayDeque<>();
       q.addLast(T);
       while(!q.isEmpty()) {
           int len = q.size();
           while (len > 0) {
               TreeNode node = q.getFirst();
               q.removeFirst();
               len--;
               if (node.left != null) {
                   if (node.left.left == null && node.left.right == null) {
                       count += node.left.val;
                   } else {
                       q.addLast(node.left);
                   }
               }
               if (node.right != null) {
                   q.addLast(node.right);
               }
           }
       }
       return count;
   }
}

